A computer database typically includes a collection of records, each of which is identified by a unique key. One technique for locating a record in such a database involves a search key and a search tree. The search tree includes nodes and leafs interconnected with branches. Each of the nodes includes data for making a branching decision at the node based on the search key. Each leaf includes a unique key associated with a record in the database. A search of the database is performed by comparing the search key with the data of a root node in the search tree and making a branching decision based on a result of that comparison to identify another node or a leaf in the search tree. This process is repeated until a leaf is identified in the search tree. In this way, the unique key associated with the record is identified.
In one type of search tree, the unique keys in the database are numerical or character strings. Moreover, each node in the search tree is associated with a common prefix of one or more unique keys in the database. Generally, the common prefix associated with the root node of the search tree is an empty string and the length of the common prefixes increase at each lower level of the search tree. This type of search tree is often referred to as a search trie. A search of the database is performed by comparing the search key with the common prefix associated with a root node of the search trie to determine the next number or character following the common prefix in the search key. A branching decision is then made based on the next number or character to identify another node or a leaf in the search trie. This process is repeated until a leaf is identified in the search tree.
In one form of a search trie, branching decisions are based on single binary digits. Moreover, each node of the search trie is associated with a common prefix of binary digits. In this form of search trie, the search key is a string of binary digits and branching decisions are made at a node of the search trie based on a distinguishing bit associated with the node. The distinguishing bit represents the next bit following the common prefix associated with the node. This type of search tree is often referred to as a digital search trie. Such a digital search trie may include a one-way branch at a node along a path from the root node to a leaf in the digital search trie. Such a path in the digital search trie may be compressed by collapsing the node with another node at a higher level of the digital search trie. This type of path-compressed digital search trie is often referred to as a Patricia trie.
Some applications require searching a computer database to find the key in the computer database having a longest common prefix with a search key. For example, an application may require searching a computer database of Internet Protocol (IP) addresses to find the IP address having a longest common prefix with a search key. In some applications, a computer database including a digital search trie is stored in a memory and a computer program is executed to search the database in the memory. In other applications, a digital search trie of a computer database is implemented in hardware to improve searching performance. Although searching performance is improved in these applications over those in which a digital search trie is stored in a memory, the hardware uses a linear decoding technique to identify a key in the digital search trie based on a search key.
In light of the above, a need exits for an improved system and method of searching a computer database for a key having a longest matching prefix with a search key.